package com.nowcoder.Offer.Heap;

import org.junit.Test;

import java.util.ArrayList;
import java.util.PriorityQueue;

/**
 * 找到最小的 k 个数
 */
public class FindMinK {

    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if(k > input.length) return new ArrayList<>();
        PriorityQueue<Integer> queue = new PriorityQueue<>((a,b)-> b-a);
        for(int i=0; i<k; i++){
            queue.offer(input[i]);
        }

        for(int j=k; j<input.length; j++){
            if(queue.peek()!=null && queue.peek() > input[j]){
                queue.poll();
                queue.offer(input[j]);
            }
        }

        return new ArrayList<>(queue);

    }

    @Test
    public void test(){
        int[] arr = {4,5,1,6,2,7,3,8};
        System.out.println(GetLeastNumbers_Solution(arr,10));
    }

}
